#if !defined(__Residues_H)
#define __Residues_H 1

// #include "backtracking.h" // just for the BT class
#include <iostream>

using namespace std; 

/* changes made in other classes or files:
 * residues (mac3all-k-residue.cpp)
 *  1. add ac3_k_residue and mac3_k_residue
 *  1.1 ac3_k_residue: use ac3_residue to compute support and initialize
 *      residues; note the destruction on residues 
 *  1.2 mac3_k_residue: introduce ac3_k_residue_propagate() and relevant 
 *      methods
 *  2. add access the csp instances
 *  2.1 BT::getPhase()
 *  2.2 CSP_Ac3::getDomSize()
 *  2.3 CSP_Ac3::isValid(...)
 *  3. performance
 *  3.1 CSP_base::num_ochecks, num_ochecks_M (the cost of sorting cache)
 *  3.2 CSP_base::addOchecks(int)
 *  3.3 CSP_base::addDchecks(int)
 */

/* to do list
 * LIFO not done
 *  get the input of which cache policy is used?
 *  set residueMethod etc. 
 * modifications of other program
 * performance statistics
 *   EXTENDED_STATISTICS not done
 */

/* C++ problems:
 * nested type declaration, e.g.,
 * BT needs Residues and Residues needs BT
 *  to use forward class definition (not able to solve all problems)
 *  to make the definition to appear only in .cpp files.
 */

#define FIFO_simple_op          10
#define FIFO_update_op          11
#define FIFO_full_op            12
#define LIFO_simple_op          20
#define LIFO_update_op          21
#define MINDOMAIN_simple_op     30
#define MINDOMAIN_update_op     31
#define MAXDOMAIN_simple_op     40
#define MAXDOMAIN_update_op     41
#define MINLEVEL_simple_op      50
#define MINLEVEL_update_op      51
#define MAXLEVEL_simple_op      60
#define MAXLEVEL_update_op      61
#define MINUSE_update_op        70
#define MINUSE_full_op          71
#define MAXUSE_update_op        80
#define MAXUSE_full_op          81

/* Residues: defines the interface for accessing and 
 * maintaining residual supports. 
 * Refer to the CPL submission on the study of residues
 */  
class BT; 
class Residues {
 protected:
  int cacheSize; // The length of the cache

  /* This cache is for value a of D_i wrt c_{ij}
   * value starts from 1 to d. 
   * variables: numbered from 0 to n-1
   */
  int vari, varj, va; 
  static BT *csp; 
  /* isValid defined as inline in residues.cpp
   * it can't be called from other files that even
   * include residues.h
   */
  // bool isValid(int b);

 
 public:
  /* Obtain the csp problem instance and the associated 
   * problem solving procedures and data.
   */
  static void setCSP(BT *csp1) { csp = csp1; }
  /* Initialize the cache size, value a and variables i and j 
   * Allocation of the cache for residues is done in the
   * derived classes of Residues. 
   */
  virtual void initialize(int k, int i, int j, int a) = 0;
  virtual bool findSupport() = 0;
  /* Add to the cache the support found from outside cache*/
  virtual void add(int b) = 0;
  /* Add the first residue to the cache. This is called before findSupport
   * and add() and called only once in solving one problem instance.
   */
  virtual void initAdd(int b) = 0;
  /* Check if the value b is in the current domain of varj */
  Residues(){};
  virtual ~Residues(){};
  void set(int k, int i1, int j1, int a1){
    cacheSize = k;
    vari = i1; 
    varj = j1; 
    va = a1;
  }
};
// define the static member
// BT *Residues::csp;

/* FIFO_simple: defines the policies for simple FIFO in managing the 
 * the residual supports. The fitness of the residues in cache
 * is not updated during the search for a support. 
 * The cache is ordered from the most recent to the least recent. 
 * The residues are in cache[0] .. cache[tail]
 */

class FIFO_simple: public Residues {
 public:
  void initialize(int, int, int, int);
  bool findSupport();
  void add(int b);
  void initAdd(int b);
  FIFO_simple()  { 
    // cout << "do nothing" << endl;
  }; 
  ~FIFO_simple() { delete [] cache; } ;

 private:
  int *cache;  
  int tail;   
};

/* FIFO_full: defines the policies for FIFO in managing the 
 * the residual supports. The fitness of both the valid support in cache
 * and the supports before it are updated during findSupport().
 * The residues are stored from cache[0] to cache[tail].
 * current is a value between 0 and tail (including).
 * The order of recentness from most recent to least recent: 
 *   cache[current] .. cache[tail] cache[0] .. cache[current-1] 
 */

class FIFO_full: public Residues {
 private: 
  int tail; // The position of the last support in the array
  int current; 
  int *cache; 

 public:
  void initialize(int, int, int, int);
  bool findSupport();
  void add(int b);
  void initAdd(int b);
  FIFO_full(){ 
    // cout << "do nothing" << endl; 
  }; 
  ~FIFO_full(){ delete [] cache; };
};

/* FIFO_update: defines the policies for FIFO in managing the 
 * the residual supports. ONLY the fitness of the valid support in cache
 * is updated.
 * The residues are stored from cache[0] to cache[tail].
 * The order of recentness from most recent to least recent: 
 *   cache[0] .. cache[tail]
 */

class FIFO_update: public Residues{
 private: 
  int tail; // The position of the last support in the array
  int *cache; 

 public:
  void initialize(int, int, int, int);
  /* findSupport: returns if a residue is in the current
   * domain. If there is one, it is moved to cache[0].
   */
  bool findSupport();
  /* add: insert b to cache[0] */
  void add(int b);
  void initAdd(int b);
  FIFO_update(){ }; 
  ~FIFO_update(){ delete [] cache; };
};

/* Node: define the pair <r,fitness> 
 * This node is used to represent the residues in 
 * cache of LEVEL, DOMAIN, and FREQUENCY based policies.
 */
class Node{
public:
  int r;
  int fitness;
  Node(){}
  ~Node(){}
};

/* Fitness_simple: Intermediate class providing helper functions
 * for LEVEL and DOMAIN based policies. 
 * During findSupport(), no fitness is updated.
 * Residues are in cache[0] ... cache[tail]. They are either 
 * ascendingly or descendingly ordered.  
 */
class Fitness_simple :public Residues {
protected:
  int tail; // The position of the last support in the array
  Node *cache; // The residual cache. cache[i] is the support 
  
public:
  void initialize(int k, int i, int j, int a);
  /* Insert a new pair <r,fitness> into cache
   * while maintaining an ascending order of fitness
   * NOTE: when fitness > cache[tail].fitness, <r,fitness>
   *   is not added in cache. 
   */
  void insInc(int r, int fitness); 
  /* Insert a new pair <r,fitness> into cache
   * while maintaining a descending order of fitness
   * NOTE: when fitness < cache[tail].fitness, <r,fitness>
   *   is not added to cache. 
   */
  void insDec(int r, int fitness); 
  /* findSupport: find the first support valid in cache 
   * from cache[0] to cache[tail].
   */
  bool findSupport(); 

  Fitness_simple() {}; 
  ~Fitness_simple() { delete [] cache; };
};

/* Fitness_update: Intermediate class providing helper functions
 * for LEVEL, DOMAIN, and FREQUENCY based policies.
 * During findSupport(), (only) the fitness of the first valid support 
 * found in the cache is updated.
 * Residues are in cache[0] ... cache[tail]. They are either 
 * ascendingly or descendingly ordered. 
 */

class Fitness_update :public Fitness_simple {
  // protected:
  // int tail; // The position of the last support in the array
  // Node *cache; 
  
public:
  /* updateInc: move the valid support at i1 in cache with
   * updated fitness to the correct position to maintain the 
   * ascending order of fitness in cache.
   */
  void updateInc(int i1, int fitness); 
  /* updateDec: move the valid support at i1 in cache with
   * updated fitness to the correct position to maintain the 
   * descending order of fitness in cache.
   */
  void updateDec(int i1, int fitness); 
  /* findSupport: find the first support valid in cache 
   * from cache[0] to cache[tail]. It also set the position
   * of the found support. 
   */
  bool findSupport(int& i);

  Fitness_update() {}; 
  ~Fitness_update() {};
};

/* MINLEVEL_simple: defines the policies for LEVEL in managing the 
 * the residual supports. It is based on Fitness_simple. 
 * NOTE. The one with min level in cache will be replaced if 
 * the level of a new support is not less than that. 
 * cache is descendingly ordered. 
 */
class MINLEVEL_simple :public Fitness_simple {

 public:
  void add(int b);
  void initAdd(int b);
  MINLEVEL_simple(){ }; 
  ~MINLEVEL_simple(){ };
};

/* MAXLEVEL_simple: defines the policies for LEVEL in managing the 
 * the residual supports. It is based on Fitness_simple. 
 * The one with max level in cache will be replaced if 
 * the level of a new support is not greater than that.  
 * cache is ascendingly ordered. 
 */
class MAXLEVEL_simple :public Fitness_simple {

 public:
  void add(int b);
  void initAdd(int b);
  MAXLEVEL_simple(){ }; 
  ~MAXLEVEL_simple(){ };
};

/* MAXDOMAIN_simple: defines the policies for DOMAIN in managing the 
 * the residual supports. It is based on Fitness_simple. 
 * The one with max domain in cache will be replaced if the domain 
 * of a new support is not greater than that.  
 * cache: ascending order
 */
class MAXDOMAIN_simple :public Fitness_simple {
 public:
  void add(int b);
  void initAdd(int b);
  MAXDOMAIN_simple(){ }; 
  ~MAXDOMAIN_simple(){ };
};

/* MINDOMAIN_simple: defines the policies for DOMAIN in managing the 
 * the residual supports. It is based on Fitness_simple. 
 * The one with min domain in cache will be replaced if the 
 * domain of a new supporte is not smaller than that.  
 * cache: descending order
 */
class MINDOMAIN_simple :public Fitness_simple {

 public:
  void add(int b);
  void initAdd(int b);
  MINDOMAIN_simple(){ }; 
  ~MINDOMAIN_simple(){ };
};

/* MINLEVEL_update: defines the policies for LEVEL in managing the 
 * the residual supports. It is based on Fitness_update. 
 * cache[0] ... cache[tail]: descending order.
 */
class MINLEVEL_update :public Fitness_update {
 public:
  bool findSupport();
  void add(int b);
  void initAdd(int b);
  MINLEVEL_update(){};
  ~MINLEVEL_update(){};
};

/* MAXLEVEL_update: defines the policies for LEVEL in managing the 
 * the residual supports. It is based on Fitness_update. 
 * cache[0] ... cache[tail]: ascending order.
 */
class MAXLEVEL_update :public Fitness_update {
 public:
  void add(int b);
  void initAdd(int b);
  bool findSupport();
  MAXLEVEL_update(){ }; 
  ~MAXLEVEL_update(){ };
};

/* MINDOMAIN_update: defines the policies for DOMAIN in managing the 
 * the residual supports. It is based on Fitness_update. 
 * cache[0] ... cache[tail]: descending order.
 */
class MINDOMAIN_update :public Fitness_update {
public:
  void add(int b);
  void initAdd(int b);
  bool findSupport();
  MINDOMAIN_update(){ }; 
  ~MINDOMAIN_update(){ };
};

/* MAXDOMAIN_update: defines the policies for DOMAIN in managing the 
 * the residual supports. It is based on Fitness_update. 
 * cache[0] ... cache[tail]: ascending order.
 */
class MAXDOMAIN_update :public Fitness_update {
public:
  void add(int b);
  void initAdd(int b);
  bool findSupport() ;

  MAXDOMAIN_update(){ }; 
  ~MAXDOMAIN_update(){ };
};

/* MAXUSE_update: Frequency based policy. The support with max 
 * usage frequency is replaced. NOTE: if the frequency of the
 * new support is larger than the max one in cache, no replacement
 * occurs. 
 * cache[0] ... cache[tail]: ascending order
 */
class MAXUSE_update :public Fitness_update{
public:
  void initAdd(int b) {
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = 1;
  };
  bool findSupport();
  void add(int b) {insInc(b, 1);};
  MAXUSE_update(){}
  ~MAXUSE_update(){}
};

/* MINUSE_update: Frequency based policy. The support with min 
 * usage frequency is replaced. NOTE: if the frequency of the
 * new support is smaller than the max one in cache, no replacement
 * occurs. 
 * cache[0] ... cache[tail]: descending order
 */
class MINUSE_update :public Fitness_update{
public:
  void initAdd(int b) {
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = 1;
  };
  bool findSupport();
  void add(int b) { insDec(b, 1);};
  MINUSE_update(){}
  ~MINUSE_update(){}
};

/* MINUSE_full: Frequency based policy. The support with min
 * usage frequency is replaced. The fitness of  both the first valid 
 * support in cache and the supports before it is updated. 
 * NOTE: if the frequency of the
 * new support is smaller than the max one in cache, no replacement
 * occurs. 
 * cache[0] ... cache[tail]: descending order
 */
class MINUSE_full :public Fitness_simple{
private:
  Node *temp;
public:
  bool findSupport();
  void add(int b) { insDec(b, 1);};
  void initAdd(int b) {
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = 1;
    try{
      temp = new Node [cacheSize];
    }
    catch(bad_alloc){
      cerr << "Memory Allocation Error" << endl;
    }
  };
  MINUSE_full(){ temp = NULL;  };
  ~MINUSE_full(){ if (temp != NULL) delete [] temp; };
};


/* MAXUSE_full: Frequency based policy. The support with max
 * usage frequency is replaced. The fitness of  both the first valid 
 * support in cache and the supports before it is updated. 
 * NOTE: if the frequency of the new support greater than the 
 * max one in cache, no replacement occurs. 
 * cache[0] ... cache[tail]: ascending order
 */
class MAXUSE_full :public Fitness_simple{
private:
  Node *temp;
public:
  bool findSupport();
  void add(int b) { insInc(b, 1);};
  void initAdd(int b) {
    tail = 0;
    cache[0].r = b;
    cache[0].fitness = 1;
    try{
      temp = new Node [cacheSize];
    }
    catch(bad_alloc){
      cerr << "Memory Allocation Error" << endl;
    }
  };
  MAXUSE_full(){ temp = NULL; };
  ~MAXUSE_full(){ if (temp != NULL) delete [] temp; };
};
#endif
